1
Условия оптимальности для равенств
MATH008Lesson 10
00:00
Представьте физическую систему, например, висящую цепь, стремящуюся к состоянию с минимальной энергией. Если концы закреплены, система не может свободно перемещаться. Оптимальность достигается тогда, когда внутренние силы (градиент потенциальной энергии) идеально уравновешиваются натяжением, создаваемым ограничениями. В выпуклой оптимизации это равновесие описывается условия ККТ для равенств.

Геометрия допустимости

Для выпуклой задачи с условиями равенства $Ax=b$, вектор $v \in \mathbf{R}^n$ является допустимым направлением если $Av = 0$. Это означает, что движение в направлении $v$ сохраняет ограничение: $A(x+v) = b$, если $Ax=b$.

Чтобы $x^*$ было оптимальным, направляющая производная $\nabla f(x^*)^T v$ должна быть равна нулю для всех допустимых направлений $v$ в нулевом пространстве $\mathcal{N}(A)$. Это означает, что градиент $\nabla f(x^*)$ должен быть ортогональным $\mathcal{N}(A)$, что приводит нас к существованию множителей Лагранжа.

Условие оптимальности

Точка $x^*$ является оптимальной тогда и только тогда, когда существует вектор $\nu^* \in \mathbb{R}^p$, такой что:

$\nabla f(x^*) + A^T \nu^* = 0$

Это образует систему линейных уравнений, характеризующих равновесие между спуском по целевой функции и многообразием ограничений.

Проекция градиента

Проекция евклидовой проекции отрицательного градиента $-\nabla f(x)$ на нулевое пространство $\mathcal{N}(A)$ задаётся формулой:

$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$

Этот вектор представляет собой «лучшее» допустимое направление спуска. Критически важно, что $x$ является оптимальным тогда и только тогда, когда $\Delta x_{\text{pg}} = 0$.

Система ККТ и свойства матрицы

Мы можем одновременно решить уравнения для шага Ньютона и двойственных переменных, используя блочную систему:

$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$

Примечание о спектральных свойствах матрицы: Матрица ККТ симметрична, но неопределённая. Если матрица невырождена, она имеет ровно $n$ положительных и $p$ отрицательных собственных значений. Это означает, что оптимальная точка $(x^*, \nu^*)$ является точкой седла функции Лагранжа $L(x, \nu) = f(x) + \nu^T(Ax-b)$, а не простым локальным минимумом в объединённом пространстве прямых и двойственных переменных.

🎯 Основной принцип
Оптимальность в задачах с равенствами требует, чтобы градиент был ортогональным нулевому пространству ограничений. Это позволяет интерпретировать шаг Ньютона как решение линейного приближения условий ККТ.